#pragma once

#include <vector>

namespace solution_057
{

class Solution
{
public:
    std::vector< std::vector<int> > insert(
            std::vector< std::vector<int> >& intervals, std::vector<int>& newInterval)
    {
        int pos = 0;
        while (pos < (int)intervals.size() && intervals.at(pos).front() < newInterval.front())
            ++pos;
        if (pos && intervals.at(pos - 1).back() >= newInterval.front()) {
            intervals.at(pos - 1).back() = std::max(intervals.at(pos - 1).back(), newInterval.back());
            --pos;
        } else {
            intervals.insert(intervals.begin() + pos, newInterval);
        }

        int next_pos = pos + 1;
        while (next_pos < (int)intervals.size()) {
            auto& interval = intervals.at(pos);
            auto& next_interval = intervals.at(next_pos);
            if (interval.back() >= next_interval.front())
                interval.back() = std::max(interval.back(), next_interval.back());
            else
                break;
            ++next_pos;
        }
        intervals.erase(intervals.cbegin() + pos + 1, intervals.cbegin() + next_pos);

        return intervals;
    }
};

}  /* namespace solution_057 */
